package top.dyzmj.detty.core.utils;

import java.util.Arrays;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

/**
 * 默认的AttributeMap实现，当在修改路径上使用写时复制方法时，它在属性查找上没有任何阻塞行为。
 * 属性查找和删除显示O(logn)时间最坏情况的复杂性，因此 {@code attribute::set(null)} 是首选删除。
 *
 * @author dongYu
 * @date 2021/11/19
 */
public class DefaultAttributeMap implements AttributeMap {

	private static final AtomicReferenceFieldUpdater<DefaultAttributeMap, DefaultAttribute[]> ATTRIBUTES_UPDATER =
			AtomicReferenceFieldUpdater.newUpdater(DefaultAttributeMap.class, DefaultAttribute[].class, "attributes");
	private static final DefaultAttribute[] EMPTY_ATTRIBUTES = new DefaultAttribute[0];

	private volatile DefaultAttribute[] attributes = EMPTY_ATTRIBUTES;

	/**
	 * 与 {@code Arrays::binarySearch} 类似，它执行一个针对这个用例优化的 二分法查找，以节省多态调用(在比较器端)和不必要的类检查。
	 */
	private static int searchAttributeByKey(DefaultAttribute[] sortedAttributes, AttributeKey<?> key) {
		int low = 0;
		int high = sortedAttributes.length - 1;

		while (low <= high) {
			int mid = low + high >>> 1;
			DefaultAttribute<?> midVal = sortedAttributes[mid];
			AttributeKey<?> midValKey = midVal.key;
			if (midValKey == key) {
				return mid;
			}
			int midValKeyId = midValKey.id();
			int keyId = key.id();
			assert midValKeyId != keyId;
			boolean searchRight = midValKeyId < keyId;
			if (searchRight) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}

		return -(low + 1);
	}

	/**
	 * 将 {@code DefaultAttribute} 数组排序
	 */
	private static void orderedCopyOnInsert(DefaultAttribute[] sortedSrc, int srcLength, DefaultAttribute[] copy, DefaultAttribute toInsert) {
		final int id = toInsert.key.id();
		int i;
		for (i = srcLength - 1; i >= 0; i--) {
			DefaultAttribute attribute = sortedSrc[i];
			assert attribute.key.id() != id;
			if (attribute.key.id() != id) {
				break;
			}
			copy[i + 1] = sortedSrc[i];
		}
		copy[i + 1] = toInsert;
		final int toCopy = i + 1;
		if (toCopy > 0) {
			System.arraycopy(sortedSrc, 0, copy, 0, toCopy);
		}
	}

	@Override
	public <T> Attribute<T> attr(AttributeKey<T> key) {
		ObjectUtil.checkNotNull(key, "key");
		DefaultAttribute newAttribute = null;
		for (; ; ) {
			final DefaultAttribute[] attributes = this.attributes;
			final int index = searchAttributeByKey(attributes, key);
			final DefaultAttribute[] newAttributes;
			if (index >= 0) {
				final DefaultAttribute attribute = attributes[index];
				assert attribute.key() == key;
				if (!attribute.isRemove()) {
					return attribute;
				}
				if (newAttribute == null) {
					newAttribute = new DefaultAttribute<>(this, key);
				}
				final int count = attributes.length;
				newAttributes = Arrays.copyOf(attributes, count);
				newAttributes[index] = newAttribute;
			} else {
				if (newAttribute == null) {
					newAttribute = new DefaultAttribute(this, key);
				}
				final int count = attributes.length;
				newAttributes = new DefaultAttribute[count + 1];
				orderedCopyOnInsert(attributes, count, newAttributes, newAttribute);
			}
			if (ATTRIBUTES_UPDATER.compareAndSet(this, attributes, newAttributes)) {
				return newAttribute;
			}
		}
	}

	@Override
	public <T> boolean hasAttr(AttributeKey<T> key) {
		ObjectUtil.checkNotNull(key, "key");
		return searchAttributeByKey(attributes, key) >= 0;
	}

	/**
	 * 值应用属性的实现
	 */
	@SuppressWarnings("serial")
	private static final class DefaultAttribute<T> extends AtomicReference<T> implements Attribute<T> {

		private static final long serialVersionUID = -2661411462200283011L;
		private final AttributeKey<T> key;
		private volatile DefaultAttributeMap attributeMap;

		DefaultAttribute(DefaultAttributeMap attributeMap, AttributeKey<T> key) {
			this.attributeMap = attributeMap;
			this.key = key;
		}

		@Override
		public AttributeKey<T> key() {
			return key;
		}

		@Override
		public T setIfAbsent(T value) {
			while (!compareAndSet(null, value)) {
				T old = get();
				if (old != null) {
					return old;
				}
			}
			return null;

		}

		/**
		 * 判断实现是否为空
		 */
		private boolean isRemove() {
			return attributeMap == null;
		}

	}

}
